package leetcode.pre100;

import java.util.*;

/**
 * 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * <p>
 * 说明：解集不能包含重复的子集。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,2,2]
 * 输出:
 * [
 * [2],
 * [1],
 * [1,2,2],
 * [2,2],
 * [1,2],
 * []
 * ]
 *
 * 相似问题见{@link leetcode.a_总结分布.Code08_组合问题}
 * @since 2020/6/10 0010 下午 7:48
 */
public class Code90_子集2 {
    public List<List<Integer>> res;


    public List<List<Integer>> subsetsWithDup(int[] nums) {
        res = new LinkedList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        //先排序，为了去重方便
        Arrays.sort(nums);
        Stack<Integer> stack = new Stack<>();
        process(nums, 0, stack);
        return res;
    }

    private  void process(int[] nums, int index, Stack<Integer> stack) {
        res.add(new ArrayList<>(stack));
        if (index == nums.length) {
            return;
        }
        for (int i = index; i < nums.length; i++) {
            if(i > index && nums[i] == nums[i - 1]){
                continue;
            }
            stack.push(nums[i]);
            process(nums, i + 1, stack);
            stack.pop();
        }
    }
}
